

#include <matrix.h>
#include <sudoku.h>
#include <sdk_list.h>

#include <string.h>

long _sdk_memory = 0;

sudoku *sdk_copy_sudoku(sudoku *sdk){

  sudoku *copy = SDK_SUDOKU_ALLOC();

#ifdef _DEBUG
  fprintf(stderr, "[sdk_copy_sudoku] Copying sudoku: ");
#endif
  
  int i, j;
  for ( i = 0; i < SDK_SIZE; i++){
    for ( j = 0; j < SDK_SIZE; j++){
      SDK_SET(copy, i, j, SDK_ELEM(sdk, i, j));
      sdk_list_copy_dest(&SDK_ELEM(copy, i, j).pos, &SDK_ELEM(sdk, i, j).pos);
    }
  }

#ifdef _DEBUG
  fprintf(stderr, "OK\n");
#endif

  return copy;

}

void _sdk_clean_sudoku(sudoku *sdk){

  memset(sdk, 0, sizeof(sudoku));

}

void sdk_free_sudoku(sudoku *sdk){

  int i, j;
  for ( i = 0; i < SDK_SIZE; i++){
    for ( j = 0; j < SDK_SIZE; j++){
      sdk_list_destroy_elems(&SDK_ELEM(sdk, i, j).pos);
    }
  }
  
  _sdk_memory -= sizeof(sdk);
  free(sdk);

}

sudoku *sdk_load_sudoku(char *sdk_path){

  vm_matrix *tmp = vm_read_matrix(sdk_path);
  if (tmp == NULL){
#ifdef _DEBUG
    fprintf(stderr, "[sdk_load_sudoku] Could not load sudoku: %s\n", sdk_path);
#endif
    return NULL;
  }

  if (tmp->rows != SDK_SIZE || tmp->columns != SDK_SIZE){
#ifdef _DEBUG
    fprintf(stderr, "[sdk_load_sudoku] Invalid matrix size: [%d:%d]\n", 
	    tmp->rows, tmp->columns);
#endif
    return NULL;
  }
#ifdef _DEBUG
  fprintf(stderr, "[sdk_load_sudoku] Read matrix: good\n");
  fprintf(stderr, "[sdk_load_sudoku] Size: [%d:%d]\n", 
	  tmp->rows, tmp->columns);
#endif

  sudoku *sdk = SDK_SUDOKU_ALLOC();
  sdk->solved = 0;
  
#ifdef _DEBUG
  fprintf(stderr, "[sdk_load_sudoku] Copying mtx values\n");
#endif

  int i, j;
  for ( i = 0; i < SDK_SIZE; i++){
    for ( j = 0; j < SDK_SIZE; j++){
      SDK_SET_VAL(sdk, i, j, tmp->data[i][j]);
      SDK_ELEM(sdk, i, j).row = i;
      SDK_ELEM(sdk, i, j).col = j;
    }
  }

  vm_free_matrix(tmp);

/*int fleshing = 1;
  int cur_sols = sdk_number_solutions(sdk);

#ifdef _DEBUG
  fprintf(stderr, "[sdk_load_sudoku] Pre-fleshing sudoku:\n");
  _sdk_print_sdk_vals(sdk);
  fprintf(stderr, "[sdk_load_sudoku] Fleshing:\n");
#endif
*/
  /* Flesh what ever values out we can. */
/*while (fleshing){

#ifdef _DEBUG
    fprintf(stderr, "[sdk_load_sudoku] Generating possibility lists\n");
#endif

    for ( i = 0; i < SDK_SIZE; i++){
      for ( j = 0; j < SDK_SIZE; j++){
	_sdk_square_possibilities(sdk, i, j);
      }
    }

#ifdef _DEBUG
    fprintf(stderr, "[sdk_load_sudoku] Generated possibilities: ok\n");
#endif

    sdk_update_values(sdk);
    int tmp_sols = sdk_number_solutions(sdk);
    if (cur_sols == tmp_sols){
      fleshing = 0;
    }
    cur_sols = tmp_sols;

#ifdef _DEBUG
    fprintf(stderr, "[sdk_load_sudoku] Number of solutions: %d\n", cur_sols);
#endif

  }
*/

  _sdk_flesh_sdk(sdk);

#ifdef _DEBUG
  fprintf(stderr, "[sdk_load_sudoku] Fleshing done\n");
#endif

  return sdk;

}

void sdk_update_values(sudoku *sdk){

  int i, j;
  for ( i = 0; i < SDK_SIZE; i++){
    for ( j = 0; j < SDK_SIZE; j++){
      if (sdk_list_length(&SDK_ELEM(sdk, i, j).pos) == 1){
	SDK_ELEM(sdk, i, j).value = 
	  sdk_list_get_elem(&SDK_ELEM(sdk, i, j).pos, 0)->num;
      }
    }
  }

}

void _sdk_update_list(sudoku *sdk, int row, int col){

  sdk_square *sqr = &SDK_ELEM(sdk, row, col);

  if (sqr->value == 0) return;
  int i = 0;
  for ( ; i < SDK_SIZE; i++){
    if (i == sqr->value) continue;
    sdk_list_destroy_num(&sqr->pos, i);
  }

}

void sdk_update_lists(sudoku *sdk){

  int i, j;
  for ( i = 0; i < SDK_SIZE; i++){
    for ( j = 0; j < SDK_SIZE; j++){
      _sdk_update_list(sdk, i, j);
    }
  }

}

int sdk_number_solutions(sudoku *sdk){
  
  int i, j, counter = 0;
  for ( i = 0; i < SDK_SIZE; i++){
    for ( j = 0; j < SDK_SIZE; j++){
      if (sdk_list_length(&SDK_ELEM(sdk, i, j).pos) == 1){
	counter++;
      }
    }
  }
  return counter;

}

sdk_sub_mtx *sdk_enclosing_matrix(sudoku *sdk, int row, int col){

  int r = (int) (row / 3);
  int c = (int) (col / 3);

  return _sdk_sub_mtx(sdk, r, c);

}

sdk_list *_sdk_new_full_list(){

  sdk_list *list = sdk_list_create();
  int i;

  for ( i = 0; i < SDK_HIGH_NUM; i++){
    sdk_list_add_num(list, i+1);
  }

  return list;

}

void _sdk_set_solved_list(sdk_list *list, int num){

  if (list->next == NULL){ // This list is empty; just add the number.
    sdk_list_add_num(list, num);
    return;
  } else if (sdk_list_length(list) == 1){
    list->next->num = num;
    return;
  } else {
    int i = 1;
    for ( ; i < SDK_SIZE + 1; i++){
      sdk_list_destroy_num(list, i);
    }
    sdk_list_add_num(list, num);
    return;
  }
  

}

int _sdk_square_possibilities(sudoku *sdk, int row, int col){

  //fprintf(stderr, "[_sdk_square_possibilities] Start mem: %ld\n", 
	  //_sdk_memory);

  if (SDK_ELEM(sdk, row, col).value != 0){ // This square is solved

    _sdk_set_solved_list(&SDK_ELEM(sdk, row, col).pos, 
			 SDK_ELEM(sdk, row, col).value);
    //fprintf(stderr, "[_sdk_square_possibilities] End mem (1): %ld\n", 
	    //_sdk_memory);
    return 1;
  }

  //fprintf(stderr, "[_sdk_square_possibilities] Point A: %ld\n", _sdk_memory);

  /* Make the sdk_sqaure's possibility list. */
  sdk_list *tmp;
  if (SDK_ELEM(sdk, row, col).pos.next == NULL){
    tmp = _sdk_new_full_list();
    memcpy(&SDK_ELEM(sdk, row, col).pos, tmp, sizeof(sdk_list));
    sdk_list_destroy(tmp);
  }

  //fprintf(stderr, "[_sdk_square_possibilities] Point B: %ld\n", _sdk_memory);

  /* Get rid of the numbers in the boxes. */
  int i, j;

  sdk_sub_mtx *sub_mtx = sdk_enclosing_matrix(sdk, row, col);
  //fprintf(stderr, "[_sdk_square_possibilities] Point B.a: %ld\n", 
          //_sdk_memory);
  for ( i = 0; i < SDK_SUB_MTX_SIZE; i++){
    for ( j = 0; j < SDK_SUB_MTX_SIZE; j++){
      if (SDK_ELEM(sub_mtx, i, j).value == 0) continue;
      sdk_list_destroy_num(&SDK_ELEM(sdk, row, col).pos,
			   SDK_ELEM(sub_mtx, i, j).value);
      //fprintf(stderr, "[_sdk_square_possibilities] Point B.b: %ld\n", 
	      //_sdk_memory);
    }
  }
  _sdk_memory -= sizeof(sdk_sub_mtx);
  free(sub_mtx);

  //fprintf(stderr, "[_sdk_square_possibilities] Point C: %ld\n", _sdk_memory);

  /* Get rid of the numbers in the rows/columns. */
  sdk_rc *rc_row = _sdk_generate_rc(sdk, row, SDK_ROW);
  sdk_rc *rc_col = _sdk_generate_rc(sdk, col, SDK_COL);

  for ( i = 0; i < SDK_SIZE; i++){
    if (rc_row->sdk_data[i].value != 0){
      sdk_list_destroy_num(&SDK_ELEM(sdk, row, col).pos, 
			   rc_row->sdk_data[i].value);
    }
    if (rc_col->sdk_data[i].value != 0){
      sdk_list_destroy_num(&SDK_ELEM(sdk, row, col).pos, 
			   rc_col->sdk_data[i].value);
    }
  }
  _sdk_memory -= sizeof(sdk_rc) + sizeof(sdk_rc);
  free((void *)rc_row);
  free((void *)rc_col);

  //fprintf(stderr, "[_sdk_square_possibilities] End mem (2): %ld\n", 
	  //_sdk_memory);
  return sdk_list_length(&SDK_ELEM(sdk, row, col).pos);

}

sdk_sub_mtx_overlay *_sdk_sub_mtx_overlay(sudoku *sdk, int sm_row, int sm_col){

  int i, j;
  int row = 0, col = 0;

  sdk_sub_mtx_overlay *mtx = SDK_SUB_MTX_OVERLAY_ALLOC();

  for ( i = sm_row * 3; i < (sm_row + 1) * 3; i++){
    col = 0;
    for ( j = sm_col * 3; j < (sm_col + 1) * 3; j++){
      mtx->sdk_data[row][col++] = &SDK_ELEM(sdk, i, j);
    }
    row++;
  }

  return mtx;

}

sdk_sub_mtx *_sdk_sub_mtx(sudoku *sdk, int sm_row, int sm_col){

  sdk_sub_mtx *sub_mtx = SDK_SUB_MTX_ALLOC();

  //fprintf(stderr, "[_sdk_sub_mtx] Subrow: %d Subcol: %d\n", sm_row, sm_col);
  //fprintf(stderr, "[_sdk_sub_mtx] Sudoku row start: %d\n", sm_row * 3);
  //fprintf(stderr, "[_sdk_sub_mtx] Sudoku col start: %d\n", sm_col * 3);

  int i, j;
  int row = 0, col = 0;

  for ( i = sm_row * 3; i < (sm_row + 1) * 3; i++){
    col = 0;
    for ( j = sm_col * 3; j < (sm_col + 1) * 3; j++){
      //fprintf(stderr, "  [_sdk_sub_mtx] val=%d\n", sqr.value);
      //fprintf(stderr, "   [_sdk_sub_mtx] mtx_row=%d mtx_col=%d\n", i, j);
      //fprintf(stderr, "   [_sdk_sub_mtx] row=%d col=%d\n", row, col);
      SDK_SET(sub_mtx, row, col++, SDK_ELEM(sdk, i, j));
    }
    row++;
  }

  return sub_mtx;

}

sdk_rc *_sdk_generate_rc(sudoku *sdk, int offset, int rc){

  sdk_rc *tmp = SDK_RC_ALLOC();
  tmp->solved = 0;
  tmp->remaining = 0;
  tmp->rc = rc;

  int i;

  if (rc == SDK_ROW){
    for ( i = 0; i < SDK_SIZE; i++){
      tmp->sdk_data[i] = SDK_ELEM(sdk, offset, i);
    }
  } else if (rc == SDK_COL){
    for ( i = 0; i < SDK_SIZE; i++){
      tmp->sdk_data[i] = SDK_ELEM(sdk, i, offset);
    }
  } else {
    _sdk_memory -= sizeof(sdk_rc);
    free((void *)tmp);
    return NULL;
  }

  return tmp;

}

/*
 * First try and find a square with only two possibilities;
 * if that doesnt work then look for one with 3, etc, until
 * a square is found. 
 */

sdk_square *_sdk_locate_branch_square(sudoku *sdk){

  int i = 2;
  for ( ; i < SDK_SIZE; i++){
    // Traverse the sudoku looking for a square with i or less possibilities
    int i, j;
    for ( i = 0; i < SDK_SIZE; i++){
      for ( j = 0; j < SDK_SIZE; j++){
	int len = sdk_list_length(&SDK_ELEM(sdk, i, j).pos);
	if (len == 1) continue;
	if (len <= i){
	  return &SDK_ELEM(sdk, i, j);
	}
      }
    }
  }

  return NULL; // If we dont find one (probably means the sudoku is solved.

}

void _sdk_die_msg(char *msg, int status){

  fprintf(stderr, "[Program Terminate] %s\n", msg);
  fprintf(stderr, "[Program Terminate] Status: %d\n", status);
  exit(status);

}

void _sdk_print_sdk_vals(sudoku *sdk){

  int i, j;

  for (i = 0; i < 3; i++){
    fprintf(stderr, "++===+===+===++===+===+===++===+===+===++\n");
    for (j = 0; j < 3; j++){
      fprintf(stderr, "][ %d | %d | %d ][ %d | %d | %d ][ %d | %d | %d ][\n",
              (int)sdk->sdk_data[(i * 3) + j][0].value,
	      (int)sdk->sdk_data[(i * 3) + j][1].value,
              (int)sdk->sdk_data[(i * 3) + j][2].value,
	      (int)sdk->sdk_data[(i * 3) + j][3].value,
              (int)sdk->sdk_data[(i * 3) + j][4].value,
	      (int)sdk->sdk_data[(i * 3) + j][5].value,
              (int)sdk->sdk_data[(i * 3) + j][6].value,
	      (int)sdk->sdk_data[(i * 3) + j][7].value,
              (int)sdk->sdk_data[(i * 3) + j][8].value);
    }
  }

  fprintf(stderr, "++===+===+===++===+===+===++===+===+===++\n");

}

void _sdk_print_pos_lists(sudoku *sdk){

  int i, j, counter = 0;

  for ( i = 0; i < SDK_SIZE; i++){
    for ( j = 0; j < SDK_SIZE; j++){
      if (sdk_list_length(&SDK_ELEM(sdk, i, j).pos) != 1){
	fprintf(stderr, "[%d:%d] ", i, j);
	_sdk_list_print_short_sum(&SDK_ELEM(sdk, i, j).pos);
	counter++;
      }
    }
  }
  fprintf(stderr, "Number of unsolved squares: %d\n", counter);

}

void _sdk_print_sub_mtx(sdk_sub_mtx *sub_mtx){

  int i, j;

  for ( i = 0; i < SDK_SUB_MTX_SIZE; i++){
    fprintf(stderr, "+---+---+---+\n");
    for ( j = 0; j < SDK_SUB_MTX_SIZE; j++){
      fprintf(stderr, "| %d ", SDK_ELEM(sub_mtx, i, j).value);
    }
    fprintf(stderr, "|\n");
  }
  fprintf(stderr, "+---+---+---+\n");

}

void _sdk_print_sub_mtx_lists(sdk_sub_mtx *sub_mtx){

  fprintf(stderr, "Sub matrix possibility lists:\n");

  int i, j;

  for ( i = 0; i < SDK_SUB_MTX_SIZE; i++){
    for ( j = 0; j < SDK_SUB_MTX_SIZE; j++){
      _sdk_list_print_short_sum(&SDK_ELEM(sub_mtx, i, j).pos);
    }
  }

}

void _sdk_print_rc(sdk_rc *rc){

  if (rc->rc == SDK_ROW){
    fprintf(stderr, "Row: ");
  } else if (rc->rc == SDK_COL){
    fprintf(stderr, "Col: ");
  } else {
    fprintf(stderr, "Badly formed sdk_rc: %d\n", rc->rc);
    return;
  }

  int i;

  fprintf(stderr, "{ ");
  for ( i = 0; i < SDK_SIZE; i++){
    fprintf(stderr, "%d ", rc->sdk_data[i].value);
  }
  fprintf(stderr, "}\n");

}

void _sdk_print_mtx_overlay(sdk_sub_mtx_overlay *mtx){

  int i, j;
  for ( i = 0; i < SDK_SUB_MTX_SIZE; i++){
    for ( j = 0; j < SDK_SUB_MTX_SIZE; j++){
#ifdef _SDK_PROC_x86_64
      fprintf(stderr, "[%d:%d]: address=0x%016lx value=%d pos:",
	      i, j, (unsigned long) mtx->sdk_data[i][j], 
	      mtx->sdk_data[i][j]->value);
#else
      fprintf(stderr, "[%d:%d]: address=0x%08lx value=%d pos:",
	      i, j, (unsigned long) mtx->sdk_data[i][j], 
	      mtx->sdk_data[i][j]->value);
#endif
      _sdk_list_print_short_sum(&mtx->sdk_data[i][j]->pos);
    }
  }

}
